﻿using System;
using System.Collections.Generic;

namespace SpatialHashLib.Topology.Indexing
{
    public partial class SpatialHash<T>
    {
        double minCellSize;

        Chain<SpatialValue> items;
        Grid[] grids;

        int version;
        int searchVersion;

        public SpatialHash(double minCellSize, int depth)
        {
            this.minCellSize = minCellSize;

            items = new Chain<SpatialValue>();
            grids = new Grid[Math.Max(depth, 1)];

            double cellSize = minCellSize;

            for (int i = 0; i < grids.Length; i++)
            {
                grids[i] = new Grid(cellSize, i);
                cellSize *= 2;
            }
        }

        public IEnumerable<T> this[ISpatialKey key]
        {
            get
            {
                ++version;
                searchVersion = version;
                return GetItems(key, grids[grids.Length - 1]);
            }
        }

        public void Add(T item, ISpatialKey key)
        {
            Grid grid;
            int depth = grids.Length - 1;

            Extent extent = key.Extent;
            double size = extent.Size;

            do
            {
                grid = grids[depth];

                foreach (CellCoord coord in new CellExtent(extent, grid.CellSize).CellCoords)
                    if (key.Intersects(coord.ToExtent(grid.CellSize)))
                        Add(item, extent, coord, grid, SizeInGrid(size, grid));

                --depth;
            }
            while (size < grid.CellSize * 0.5 && depth >= 0);
        }

        public void Remove(T item, ISpatialKey key)
        {
            Grid grid;
            int depth = grids.Length - 1;

            Extent extent = key.Extent;
            double size = extent.Size;

            do
            {
                grid = grids[depth];

                foreach (CellCoord coord in new CellExtent(extent, grid.CellSize).CellCoords)
                    if (key.Intersects(coord.ToExtent(grid.CellSize)))
                        Remove(item, extent, coord, grid, SizeInGrid(size, grid));

                --depth;
            }
            while (size < grid.CellSize * 0.5 && depth >= 0);
        }

        public void Change(T item, ISpatialKey oldKey, ISpatialKey newKey)
        {
            Grid grid;
            int depth = grids.Length - 1;

            Extent oldExtent = oldKey.Extent;
            Extent newExtent = newKey.Extent;

            double oldSize = oldKey.Extent.Size;
            double newSize = newKey.Extent.Size;

            double minSize = Math.Min(oldSize, newSize);

            bool oldInGrid;
            bool newInGrid;

            bool removeOld;
            bool addNew;

            bool sameGrid;
            bool sameAncestor;

            CellExtent oldCellExtent;
            CellExtent newCellExtent;

            do
            {
                grid = grids[depth];

                removeOld = oldSize < grid.CellSize || (oldSize >= grid.CellSize * 0.5 && depth == grids.Length - 1);
                addNew = newSize < grid.CellSize || (newSize >= grid.CellSize * 0.5 && depth == grids.Length - 1);

                oldInGrid = SizeInGrid(oldSize, grid);
                newInGrid = SizeInGrid(newSize, grid);

                sameGrid = oldInGrid && newInGrid;
                sameAncestor = removeOld && addNew && !(oldInGrid || newInGrid);

                if (sameGrid || sameAncestor)
                {
                    oldCellExtent = new CellExtent(oldExtent, grid.CellSize);
                    newCellExtent = new CellExtent(newExtent, grid.CellSize);

                    foreach (CellCoord coord in oldCellExtent.CellCoords)
                        if (!coord.InCellExtent(newCellExtent) && oldKey.Intersects(coord.ToExtent(grid.CellSize)))
                            Remove(item, oldExtent, coord, grid, oldInGrid);

                    foreach (CellCoord coord in newCellExtent.CellCoords)
                        if (!coord.InCellExtent(oldCellExtent) && newKey.Intersects(coord.ToExtent(grid.CellSize)))
                            Add(item, newExtent, coord, grid, newInGrid);
                }
                else
                {
                    if (removeOld)
                        foreach (CellCoord coord in new CellExtent(oldExtent, grid.CellSize).CellCoords)
                            if (oldKey.Intersects(coord.ToExtent(grid.CellSize)))
                                Remove(item, oldExtent, coord, grid, oldInGrid);

                    if (addNew)
                        foreach (CellCoord coord in new CellExtent(newExtent, grid.CellSize).CellCoords)
                            if (newKey.Intersects(coord.ToExtent(grid.CellSize)))
                                Add(item, newExtent, coord, grid, newInGrid);
                }

                --depth;
            }
            while (minSize < grid.CellSize * 0.5 && depth >= 0);
        }

        #region Private Methods

        IEnumerable<T> GetItems(ISpatialKey key, Grid grid)
        {
            Cell cell;
            int itemIndex;
            SpatialValue item;

            foreach (var coord in GetCoords(key, grid))
                if (grid.ContainsKey(coord))
                {
                    #region Report cell search (if in DEBUG mode)
#if DEBUG
                    OnCellSearch(coord.Row, coord.Col, grid.CellSize);
#endif
                    #endregion

                    cell = grid[coord];
                    itemIndex = items.Next(cell.ChainIndex);

                    #region Return each item that hasn't already been returned

                    for (int i = 0; i < cell.ItemCount; i++)
                    {
                        if (version > searchVersion)
                            throw new InvalidOperationException("Collection has changed; iteration cannot continue.");

                        item = items[itemIndex];

                        if (item.Version < version)
                        {
                            item.Version = version;
                            yield return item.Item;
                        }

                        itemIndex = items.Next(itemIndex);
                    }

                    #endregion

                    #region Search each cell covered by this cell in the next grid

                    if (grid.Index > 0)
                    {
                        foreach (
                            T childItem in GetItems(
                                coord.ToExtent(grid.CellSize).Intersection(key.Extent),
                                grids[grid.Index - 1]
                                )
                            )
                            yield return childItem;
                    }

                    #endregion
                }
        }

        void Add(T item, Extent extent, CellCoord coord, Grid grid, bool inGrid)
        {
            Cell cell;

            if (!grid.ContainsKey(coord))
                cell = AddCell(coord, grid);
            else
                cell = grid[coord];

            if (inGrid)
            {
                ++cell.ItemCount;
                items.AddAfter(new SpatialValue(item), cell.ChainIndex);
            }
            else
                ++cell.ChildCount;

            grid[coord] = cell;
        }

        void Remove(T item, Extent extent, CellCoord coord, Grid grid, bool inGrid)
        {
            Cell cell;

            if (grid.ContainsKey(coord))
            {
                cell = grid[coord];

                if (inGrid)
                {
                    int itemIndex = items.Next(cell.ChainIndex);
                    int itemCount = cell.ItemCount;

                    for (int i = 0; i < itemCount; i++)
                    {
                        if (items[itemIndex].Item.Equals(item))
                        {
                            items.Remove(itemIndex);
                            --cell.ItemCount;

                            if (cell.ItemCount == 0 && cell.ChildCount == 0)
                                RemoveCell(cell, coord, grid);
                            else
                                grid[coord] = cell;

                            break;
                        }

                        itemIndex = items.Next(itemIndex);
                    }
                }
                else
                {
                    --cell.ChildCount;

                    if (cell.ChildCount == 0 && cell.ItemCount == 0)
                        RemoveCell(cell, coord, grid);
                    else
                        grid[coord] = cell;
                }
            }
        }

        bool SizeInGrid(double size, Grid grid)
        {
            return
                grid.Index == grids.Length - 1 ?
                    size >= grid.CellSize * 0.5 :
                    grid.Index > 0 ?
                        size < grid.CellSize && size * 2 >= grid.CellSize :
                        size < grid.CellSize
                        ;
        }

        IEnumerable<CellCoord> GetCoords(ISpatialKey key, Grid grid)
        {
            CellExtent extent = new CellExtent(key.Extent, grid.CellSize);
            CellCoord coord;

            for (int row = extent.Min.Row; row < extent.Max.Row; row++)
                for (int col = extent.Min.Col; col < extent.Max.Col; col++)
                {
                    coord = new CellCoord(row, col);
                    if (key.Intersects(coord.ToExtent(grid.CellSize)))
                        yield return coord;
                }
        }

        Cell AddCell(CellCoord coord, Grid grid)
        {
            Cell cell = new Cell(items.AddLast(null));

            #region Report cell added (if in DEBUG mode)
#if DEBUG
            OnCellAdded(coord.Row, coord.Col, grid.CellSize);
#endif
            #endregion

            return cell;
        }

        void RemoveCell(Cell cell, CellCoord coord, Grid grid)
        {
            items.Remove(cell.ChainIndex);
            grid.Remove(coord);

            #region Report cell removed (if in DEBUG mode)
#if DEBUG
            OnCellRemoved(coord.Row, coord.Col, grid.CellSize);
#endif
            #endregion
        }

        #endregion
    }
}
